package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * <a href="https://leetcode.cn/problems/group-anagrams/">字母异位词分组(Group Anagrams)</a>
 * <p>给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。</p>
 * <p>字母异位词 是由重新排列源单词的所有字母得到的一个新单词。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
 *      输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
 *
 * 示例 2:
 *      输入: strs = [""]
 *      输出: [[""]]
 *
 * 示例 3:
 *      输入: strs = ["a"]
 *      输出: [["a"]]
 *     </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= strs.length <= 10^4</li>
 *         <li>0 <= strs[i].length <= 100</li>
 *         <li>strs[i] 仅包含小写字母</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/11 14:03
 */
public class LC0049GroupAnagrams_M {

    static class Solution {
        public List<List<String>> groupAnagrams(String[] strs) {
            Map<String, List<String>> retMap = new HashMap<>();
            for (String sourceStr : strs) {
                char[] chars = sourceStr.toCharArray();
                Arrays.sort(chars);
                String sortedStr = new String(chars);
                retMap.computeIfAbsent(sortedStr, e -> new ArrayList<>()).add(sourceStr);
            }
            return new ArrayList<>(retMap.values());
        }

        public List<List<String>> groupAnagrams2(String[] strs) {
            Map<String, List<String>> retMap = new HashMap<>();
            for (String sourceStr : strs) {
                // 统计字符串中的每个字符的数量
                int[] chCntArr = new int[26];
                for (char c : sourceStr.toCharArray()) {
                    ++chCntArr[c - 'a'];
                }
                // 将字符串中出现的字符按照a-z的顺序组合成新的字符串，作为 hashMap的key
                StringBuilder builder = new StringBuilder();
                for (int i = 0; i < chCntArr.length; i++) {
                    while (chCntArr[i] > 0) {
                        builder.append(i + 'a');
                        --chCntArr[i];
                    }
                }
                // 上述操作：将类似于：acbd->abcd  dcba->abcd

                retMap.computeIfAbsent(builder.toString(), e -> new ArrayList<>()).add(sourceStr);
            }
            return new ArrayList<>(retMap.values());
        }

        public List<List<String>> groupAnagrams3(String[] strs) {
            return new ArrayList<>(Arrays.stream(strs)
                    .collect(Collectors.groupingBy(sourceStr -> {
                        // 返回 str 排序后的结果。
                        // 按排序后的结果来grouping by，算子类似于 sql 里的 group by。
                        char[] chars = sourceStr.toCharArray();
                        Arrays.sort(chars);
                        return new String(chars);
                    })).values());
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<String>> lists1 = solution.groupAnagrams2(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
        for (List<String> list : lists1) {
            for (String s : list) {
                System.out.print(s + "   ");
            }
            System.out.println();
        }

        System.out.println("----------");
        List<List<String>> lists2 = solution.groupAnagrams2(new String[]{""});
        for (List<String> list : lists2) {
            for (String s : list) {
                System.out.print(s + "   ");
            }
            System.out.println();
        }

        System.out.println("----------");
        List<List<String>> lists3 = solution.groupAnagrams2(new String[]{"a"});
        for (List<String> list : lists3) {
            for (String s : list) {
                System.out.print(s + "   ");
            }
            System.out.println();
        }
        System.out.println("----------");
        List<List<String>> lists4 = solution.groupAnagrams2(new String[]{"cab", "tin", "pew", "duh", "may", "ill", "buy", "bar", "max", "doc"});
        for (List<String> list : lists4) {
            for (String s : list) {
                System.out.print(s + "   ");
            }
            System.out.println();
        }
    }
}